/*
 * Copyright (C) 2009,2010,2011  Paulo Cesar Pereira de Andrade.
 *
 * This is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This software is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * Authors:
 *	Paulo Cesar Pereira de Andrade
 */

#include "exl.h"

/*
 * Prototypes
 */
static void
basics(efunction_t *function);

static void
basic_use(east_list_t *list, east_node_t *value);

static ebool_t
basic_reload(east_list_t *base);

static void
basic_load(east_list_t *list, esymbol_t *atom);

static void
basic_load_stack(east_list_t *list, eint32_t offset);

static ebool_t
basic_store(east_list_t *base, esymbol_t *atom);

static ebool_t
basic_store_stack(east_list_t *base, eint32_t offset);

static void
basic_const(east_list_t *list, east_node_t *value);

static void
basic_predicate(east_list_t *list, ecode_t pred);

static void
basic_jump(efunction_t *function, east_list_t *list, ecode_t test);

static void
basic_unreachable(efunction_t *function, east_list_t *list);

static void
basic_note(east_list_t *list);

static void
labels(efunction_t *function);

static east_list_t *
label_code(elabel_t *label);

static void
label_shortcut(efunction_t *function);

static void
label_sequential_update(east_node_t *node, elabel_t *insert, elabel_t *remove);

static void
label_sequential(efunction_t *function, east_list_t *list, elabel_t *label);

static east_list_t *
label_redundancy(efunction_t *function, east_list_t *tail, east_node_t *node);

/*
 * Initialization
 */
static ebool_t again;

/*
 * Implementation
 */
ebool_t
eoptimize(efunction_t *function)
{
    ebool_t	change;

    again = false;
    basics(function);
    labels(function);
    if ((change = again)) {
	do {
	    /*   NOTE: this may benefit from splitting the loop in two
	     * but, if labels() modify the intermediate representation,
	     * it is required to call basics() again, or it may leave
	     * the code in an inconsistent state.
	     *   A known inconsistent state is a function that ends in
	     * an infinite loop, and the intermediate representation
	     * could be left with the bottom as:
	     *		...
	     *		jmp Lx
	     *		jmp Ly
	     *		<<<end-of-list>>>
	     * and this causes ssa_loops() to create wrong "grouping"
	     * of loops, what causes phi bits of loop headers to not
	     * be generated correctly.
	     */
	    again = false;
	    basics(function);
	    labels(function);
	} while (again);
    }

    return (change);
}

/*
 * do basic simplification, removing redundancy and simple code
 * merge, so that next passes have less data to inspect/parse
 */
static void
basics(efunction_t *function)
{
    east_node_t		*node;
    east_list_t		*list;
    east_list_t		*prev;

    for (prev = function->code, list = east_next(prev);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
		basic_const(list, node);
		break;

	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		if (basic_reload(prev))
		    list = prev;
		else
		    basic_load(list, node->csymbol.symbol);
		break;
	    case eop_ls:
		if (basic_reload(prev))
		    list = prev;
		else
		    basic_load_stack(list, node->cstack.offset);
		break;

		/* push+pop can result after removal of redundancy */
	    case eop_push:
		if (east_next(list)) {
		    node = east_node(east_next(list));
		    if (node->code == eop_pop) {
			east_next(prev) = east_next(east_next(list));
			list = prev;
			again = true;
		    }
		}
		break;

		/* pop+push can result at least from constructor calls
		 * in complex data initializations */
	    case eop_pop:
		if (east_next(list)) {
		    node = east_node(east_next(list));
		    if (node->code == eop_push) {
			east_next(list) = east_next(east_next(list));
			east_node(list) = ecode_stack_load(-1);
			list = prev;
			again = true;
		    }
		}
		break;

	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:
		if (basic_store(prev, node->csymbol.symbol))
		    list = prev;
		break;
	    case eop_ss:			case eop_sst:
	    case eop_ssv:
		if (basic_store_stack(prev, node->cstack.offset))
		    list = prev;
		break;

	    case eop_try:
		/* the jump after try is the exception non local jump target */
		list = east_next(list);
		break;

	    case eop_jf:			case eop_jt:
		basic_jump(function, list, node->code);
		break;

	    case eop_j:				case eop_ret:
	    case eop_rett:			case eop_reti:
	    case eop_retit:			case eop_exit:
	    case eop_throw:
		basic_unreachable(function, list);
		break;

	    case eop_intp_0:			case eop_nump_0:
		basic_const(list, ecode_int(0));
		basic_predicate(list, node->code);
		break;
	    case eop_intp_n1:
		basic_const(list, ecode_int(-1));
		basic_predicate(list, node->code);
		break;
	    case eop_intp_v:			case eop_realp_v:
	    case eop_nump_v:
		basic_predicate(list, node->code);
		break;

	    case eop_note:
		basic_note(list);
		break;

	    default:
		break;
	}
    }
}

/*
 * discard reload of same value interleaved
 * with code that doesn't modify implicit value
 */
static void
basic_use(east_list_t *list, east_node_t *value)
{
    east_node_t		*node;
    east_list_t		*prev;

    for (prev = list, list = east_next(list);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		if (node != value)
		    return;
		east_next(prev) = east_next(list);
		list = prev;
		again = true;
		break;
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:			case eop_ss:
	    case eop_sst:			case eop_ssv:
	    case eop_svai:			case eop_push:
	    case eop_pusht:			case eop_pushv:
	    case eop_intp_v:			case eop_realp_v:
	    case eop_nump_v:			case eop_note:
		break;
	    default:
		return;
	}
    }
}

/*
 * check for sequential redundant loads
 */
static ebool_t
basic_reload(east_list_t *base)
{
    east_list_t		*list;
    east_node_t		*node;
    ebool_t		 reload;

    if ((list = east_next(base)) == null)
	return (false);
    basic_use(list, east_node(list));
    reload = false;
    for (list = east_next(list); list; list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_note:
		break;
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:			case eop_ls:
	    case eop_pd:			case eop_pdt:
	    case eop_pb:			case eop_pbt:
	    case eop_lvai:
		east_next(base) = list;
		reload = true;
		break;
	    default:
		if (reload)
		    again = true;
		return (reload);
	}
    }
    if (reload)
	again = true;
    return (reload);
}

/*
 * check for load, store*, followed by load of the initial value
 */
static void
basic_load(east_list_t *list, esymbol_t *atom)
{
    east_node_t		*node;
    east_list_t		*prev;

    for (prev = list, list = east_next(list);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		if (node->csymbol.symbol != atom ||
		    /* load cannot be omitted if implicit value
		     * may have been truncated */
		    node->csymbol.symbol->type != t_void)
		    return;
		east_next(prev) = east_next(list);
		list = prev;
		again = true;
		break;
		/* stores don't change width/type of implicit value */
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sh:			case eop_sv:
	    case eop_svi:			case eop_sr:
	    case eop_sc:			case eop_ss:
	    case eop_sst:			case eop_ssv:
	    case eop_sref:			case eop_sva:
	    case eop_svai:			case eop_push:
	    case eop_pusht:			case eop_pushv:
		/* optimize common case 'exp1 ? exp1 : exp2' */
	    case eop_jt:			case eop_jf:
	    case eop_note:
		break;
	    default:
		return;
	}
    }
}

static void
basic_load_stack(east_list_t *list, eint32_t offset)
{
    east_node_t		*node;
    east_list_t		*prev;

    for (prev = list, list = east_next(list);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_ls:
		if (node->cstack.offset != offset)
		    return;
		east_next(prev) = east_next(list);
		list = prev;
		again = true;
		break;
		/* stores don't change width/type of implicit value */
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:			case eop_sh:
	    case eop_shref:			case eop_sv:
	    case eop_svi:			case eop_svref:
	    case eop_sr:			case eop_srref:
	    case eop_ss:			case eop_sst:
	    case eop_ssv:			case eop_sref:
	    case eop_sva:			case eop_svai:
		/* optimize common case 'exp1 ? exp1 : exp2' */
	    case eop_jt:			case eop_jf:
	    case eop_note:
		break;
	    default:
		return;
	}
    }
}

/*
 * check if can kill stores without loads in the interval
 */
static ebool_t
basic_store(east_list_t *base, esymbol_t *atom)
{
    east_list_t		*list;
    east_node_t		*node;
    east_list_t		*prev;
    east_list_t		*temp;
    ebool_t		 change;

    change = false;
    prev = east_next(base);
    for (list = east_next(prev); list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:
		if (node->csymbol.symbol == atom) {
		    /* another store, kill the previous one */
		    east_next(base) = east_next(east_next(base));
		    base = prev;
		    change = again = true;
		}
		break;
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_lc:
		if (node->csymbol.symbol == atom) {
		    /* store, load => store
		     * only valid if store doesn't truncate implicit value */
		    if (node->csymbol.symbol->type == t_void) {
			for (temp = east_next(east_next(base));
			     temp != list; temp = east_next(temp))
			    if (east_node(temp)->code != eop_note)
				return (change);
			/* don't need basic_load() in this case */
			east_next(prev) = east_next(list);
			return (again = true);
		    }
		    return (change);
		}
		break;
		/* don't attempt to be smart on basic block boundaries */
	    case eop_label:			case eop_block:
		/* lref and sref because may be a pointer to the symbol */
	    case eop_lref:			case eop_sref:
		/* obvious cases where flow is not followed */
	    case eop_j:				case eop_jt:
	    case eop_jf:			case eop_jh:
	    case eop_jv:
	    case eop_call:			case eop_blt:
	    case eop_meth:			case eop_ecm:
	    case eop_apply:
	    case eop_ret:			case eop_reti:
	    case eop_rett:			case eop_retit:
	    case eop_unwind:			case eop_throw:
		return (change);
	    default:
		/* no effect on check for redundant load */
		break;
	}
    }
    return (change);
}

static ebool_t
basic_store_stack(east_list_t *base, eint32_t offset)
{
    east_list_t		*list;
    east_node_t		*node;
    east_list_t		*prev;
    east_list_t		*temp;
    ebool_t		 change;

    change = false;
    prev = east_next(base);
    for (list = east_next(prev); list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_ss:			case eop_ssv:
	    case eop_sst:
		if (node->cstack.offset == offset) {
		    /* another store, kill the previous one */
		    east_next(base) = east_next(east_next(base));
		    base = prev;
		    change = again = true;
		}
		break;
	    case eop_ls:
		if (node->cstack.offset == offset) {
		    for (temp = east_next(east_next(base));
			 temp != list; temp = east_next(temp))
			if (east_node(temp)->code != eop_note)
			    return (change);
		    /* don't need basic_load_stack() in this case */
		    east_next(prev) = east_next(list);
		    return (again = true);
		}
		break;
		/* don't attempt to be smart on basic block boundaries */
	    case eop_label:			case eop_block:
		/* lref and sref because may be a pointer to the symbol */
	    case eop_lref:			case eop_sref:
		/* obvious cases where flow is not followed */
	    case eop_j:				case eop_jt:
	    case eop_jf:			case eop_jh:
	    case eop_jv:
	    case eop_call:			case eop_blt:
	    case eop_meth:			case eop_ecm:
	    case eop_apply:			case eop_aret:
	    case eop_ret:			case eop_reti:
	    case eop_rett:			case eop_retit:
	    case eop_unwind:			case eop_throw:
		/* anything else that modifies stack */
	    case eop_push:			case eop_pushv:
	    case eop_pop:
	    case eop_lh:			case eop_lhref:
	    case eop_sh:			case eop_shref:
	    case eop_off:			case eop_lv:
	    case eop_lvref:			case eop_sv:
	    case eop_svi:			case eop_svref:
	    case eop_pv:
	    case eop_lrref:			case eop_sr:
	    case eop_srref:
	    case eop_enter:			case eop_begin:
	    case eop_ne:			case eop_lt:
	    case eop_le:			case eop_eq:
	    case eop_ge:			case eop_gt:
	    case eop_and:			case eop_or:
	    case eop_xor:			case eop_mul2:
	    case eop_div2:			case eop_shl:
	    case eop_shr:			case eop_add:
	    case eop_sub:			case eop_mul:
	    case eop_div:			case eop_trunc2:
	    case eop_rem:			case eop_atan2:
	    case eop_pow:			case eop_hypot:
	    case eop_complex:
	    case eop_vnew:			case eop_renew:
	    case eop_szofdim:			case eop_subtpof:
	    case eop_vas:			case eop_val:
	    case eop_sva:			case eop_try:
	    case eop_catch:
		return (change);
	    default:
		/* no effect on check for redundant load */
		break;
	}
    }
    return (change);
}

/*
 * check for sequential loads of constants and jumps based on it
 */
static void
basic_const(east_list_t *list, east_node_t *value)
{
    ecode_t		 code;
    east_node_t		*node;
    east_list_t		*prev;

    for (prev = list, list = east_next(list);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	code = node->code;
	switch (code) {
		/* check for sequential constant loads */
	    case eop_nil:			case eop_int:
	    case eop_float:			case eop_ll:
		value = node;
	    change:
		east_node(prev) = node;
		east_next(prev) = east_next(list);
		list = prev;
		again = true;
		break;

		/*   Allow optimizing jumps after predicate+set, assuming
		 * there is not an exception, and if one is generated, it
		 * would either go to a catch or exit.
		 *   If the predicate is followed by another load, it is
		 * also dropped, because it is dead code, and this kind
		 * of dead code elimination is being allowed, example:
		 *	"string" & 0; 1;
		 * "silently" becomes:
		 *	1;
		 * and the "1;" should also be removed, either here or
		 * in elive.c.
		 *   That is, if the code is dropped, don't bother if it
		 * would generate a runtime error due to wrong arguments
		 */
	    case eop_intp_0:			case eop_nump_0:
		value = ecode_int(0);
		goto change;
	    case eop_intp_n1:
		value = ecode_int(-1);
		goto change;
	    case eop_intp_v:			case eop_realp_v:
	    case eop_nump_v:
		/* no side effect */
		break;

		/* check for conditional jumps depending on constant value */
	    case eop_jt:
		if (ecode_false_p(value)) {
		    /* false; jt label; next => false; next */
		    elabel_branch_remove(node->clabel.label, node);
		    east_next(prev) = east_next(list);
		}
		else
		    /* true; jt label; next => true; j label; next */
		    node->clabel.code = eop_j;
		again = true;
		return;
	    case eop_jf:
		if (ecode_false_p(value))
		    /* false; jf label; next => false; j label; next */
		    node->clabel.code = eop_j;
		else {
		    /* true; jf label; next => true; next */
		    elabel_branch_remove(node->clabel.label, node);
		    east_next(prev) = east_next(list);
		}
		again = true;
		return;

		/* check for non constant load after load of constant */
	    case eop_ld:			case eop_ldt:
	    case eop_lb:			case eop_lbt:
	    case eop_pd:			case eop_pdt:
	    case eop_pb:			case eop_pbt:
	    case eop_lc:			case eop_ls:
		east_node(prev) = node;
		east_next(prev) = east_next(list);
		again = true;
		return;

		/* check for store of constant followed by conditional jump */
	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:			case eop_ss:
	    case eop_sst:			case eop_ssv:
	    case eop_push:			case eop_pusht:
	    case eop_pushv:
		basic_use(list, value);
		prev = list;
		for (;;) {
		    if ((list = east_next(list)) == null)
			return;
		    node = east_node(list);
		    code = node->code;
		    switch (code) {
			    /* no branch condition change on multiple stores */
			case eop_sd:		case eop_sdt:
			case eop_sb:		case eop_sbt:
			case eop_sc:		case eop_ss:
			case eop_sst:		case eop_ssv:
			    /* no side effect */
			case eop_intp_v:	case eop_realp_v:
			case eop_nump_v:	case eop_note:
			    prev = list;
			    break;
			default:
			    goto check;
		    }
		}
	    check:
		if (code == eop_jt) {
		    if (ecode_false_p(value)) {
			/* store_false; jt label; next => store_false; next */
			elabel_branch_remove(node->clabel.label, node);
			east_next(prev) = east_next(list);
		    }
		    else
			/* store_true; jt label; next
			 * =>			next is unreachable
			 * store_true; j label; next */
			node->clabel.code = eop_j;
		    again = true;
		}
		else if (code == eop_jf) {
		    if (ecode_false_p(value))
			/* store_false; jf label; next
			 * =>			next is unreachable
			 * store_false; j label; next */
			node->clabel.code = eop_j;
		    else {
			/* store_true; jf label; next => store_true; next */
			elabel_branch_remove(node->clabel.label, node);
			east_next(prev) = east_next(list);
		    }
		    again = true;
		}
		return;

	    case eop_note:
		/* dont let annotations prevent removal of redundant loads */
		east_node(list) = east_node(prev);
		east_node(prev) = node;
		prev = list;
		break;

	    default:
		return;
	}
    }
}

/*
 * check for redundant predicates following another
 */
static void
basic_predicate(east_list_t *list, ecode_t pred)
{
    ecode_t		 code;
    east_node_t		*node;
    east_list_t		*prev;
    east_list_t		*tail;

    prev = tail = list;
    for (list = east_next(list); list; prev = list, list = east_next(list)) {
	node = east_node(list);
	code = node->code;
	switch (code) {

	    case eop_intp_0:
		/* intp_0 following other predicates replaces them */
	    change:
		pred = code;
		east_node(tail) = node;
	    remove:
		east_next(prev) = east_next(list);
		list = prev;
		again = true;
		break;

	    case eop_intp_v:
		switch (pred) {
		    case eop_intp_0:
		    case eop_intp_v:
			/* redundant check for integer */
			goto remove;
		    default:
			/* make this predicate the current one */
			goto change;
		}
		break;

	    case eop_realp_v:
		switch (pred) {
		    case eop_intp_0:
		    case eop_intp_v:
			/* redundant check for real number */
			goto remove;
		    default:
			/* make this predicate the current one */
			goto change;
		}
		break;

	    case eop_nump_0:
		switch (pred) {
		    case eop_intp_0:
			/* redundant number predicate and zero assignment */
			goto remove;
		    default:
			/* make this predicate the current one */
			goto change;
		}
		break;

	    case eop_nump_v:
		/* redundant check for number */
		goto remove;

	    case eop_sd:			case eop_sdt:
	    case eop_sb:			case eop_sbt:
	    case eop_sc:			case eop_ss:
	    case eop_sst:			case eop_ssv:
	    case eop_push:			case eop_pusht:
	    case eop_pushv:
	    case eop_note:
		break;

	    default:
		return;
	}
    }
}

/*
 * check for sequential conditional jump opcodes
 */
static void
basic_jump(efunction_t *function, east_list_t *list, ecode_t test)
{
    ecode_t		 code;
    east_node_t		*node;
    east_node_t		*next;
    east_node_t		*last;
    east_list_t		*prev;
    elabel_t		*prev_label;
    elabel_t		*next_label;

    for (prev = list, list = east_next(list);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	code = node->code;
	switch (code) {
	    case eop_jf:			case eop_jt:
		again = true;
		if (test == code) {
		    /* same condition, remove following jump */
		    elabel_branch_remove(node->clabel.label, node);
		    east_next(prev) = east_next(list);
		    list = prev;
		}
		else {
		    /* inverse condition, make following jump unconditional */
		    node->clabel.code = eop_j;
		    return;
		}
		break;
	    case eop_j:
		/* pattern of common code generation for 'continue':
		 *		<<test>>
		 *		jf code_label
		 *		j continue_label
		 *		code_label:
		 * that here is modified to:
		 *		<<test>>
		 *		jt continue_label
		 *		code_label:
		 */
		if (east_next(list)) {
		    next = east_node(east_next(list));
		    if (next->code != eop_label)
			return;
		    last = east_node(prev);
		    prev_label = last->clabel.label;
		    next_label = next->clabel.label;
		    if (prev_label == next_label) {
			/* get value of swaped label */
			next_label = node->clabel.label;

			/* invert jump test and swap jump targets */
			code = test == eop_jf ? eop_jt : eop_jf;
			last->clabel.code = code;

			elabel_branch_remove(node->clabel.label, node);
			elabel_branch_remove(last->clabel.label, last);

			node->clabel.label = last->clabel.label;
			last->clabel.label = next_label;

			elabel_branch_insert(node->clabel.label, node);
			elabel_branch_insert(last->clabel.label, last);

			/* cannot remove the label as it may be the target
			 * of another jump, but now label_redundancy() is free
			 * to remove it, as one less jump targets it */
			again = true;
		    }
		    return;
		}
		break;
	    case eop_note:
		/* move annotation before jump */
		east_node(list) = east_node(prev);
		east_node(prev) = node;
		break;
	    default:
		return;
	}
    }
}

/*
 * delete unreachable code after unconditional jump
 */
static void
basic_unreachable(efunction_t *function, east_list_t *list)
{
    ecode_t		 code;
    east_node_t		*node;
    east_node_t		*note;
    east_list_t		*tail;
    ecode_t		 test;

    tail = list;
    note = null;
    test = eop_noop;
    for (list = east_next(list); list; list = east_next(list)) {
	node = east_node(list);
	code = node->code;
	switch (code) {
	    case eop_label:
		goto next_block;
		/* collect only information for possible warning */
	    case eop_note:
		if (note == null)
		    note = node;
		break;
	    case eop_j:				case eop_jt:
	    case eop_jf:			case eop_exit:
		break;
	    case eop_ret:			case eop_reti:
	    case eop_rett:			case eop_retit:
		if (!(node->creturn.flags & code_return_implicit))
		    test = code;
		break;
	    default:
		/* list the proper line on possible warning */
		test = code;
		break;
	}
    }

next_block:
    if (test != eop_noop && note)
	/* if there is more then auto generated code after jump */
	enote_warn(note, "code is unreachable");

    if (east_next(tail) != list) {
	ehash_t		*hash;
	east_list_t	*temp;
	eentry_t	*entry;
	eint32_t	 offset;

	/* update target information of any removed jumps */
	for (temp = east_next(tail); temp != list; temp = east_next(temp)) {
	    node = east_node(temp);
	    switch (node->code) {
		case eop_block:
		    eremove_block(function, node->clabel.label);
		    break;
		case eop_j:			case eop_jt:
		case eop_jf:
		    elabel_branch_remove(node->clabel.label, node);
		    break;
		case eop_jh:
		    hash = els[immediate_offset(node)];
		    for (offset = 0; offset < hash->size; offset++)
			for (entry = hash->entries[offset];
			     entry; entry = entry->next) {
			    note = entry->value;
			    elabel_branch_remove(note->clabel.label, node);
			}
		    break;
		default:
		    break;
	    }
	}

	east_next(tail) = list;
	again = true;
    }
}

/*
 * merge sequential annotations
 */
static void
basic_note(east_list_t *list)
{
    ecode_t		 code;
    east_node_t		*node;
    east_node_t		*note;
    east_list_t		*prev;

    note = east_node(list);
    for (prev = list, list = east_next(list); list; list = east_next(list)) {
	node = east_node(list);
	code = node->code;
	switch (code) {
	    case eop_label:
		/* move note after label */
		east_node(prev) = node;
		east_node(list) = note;
		/* update label list information */
		elabel_list(node->clabel.label) = prev;
		prev = list;
		break;
	    case eop_note:
		/* merge sequential notes  */
		east_node(prev) = node;
		east_next(prev) = east_next(list);
		note = node;
		list = prev;
		break;
	    default:
		return;
	}
    }
}

static void
labels(efunction_t *function)
{
    east_node_t		 *node;
    east_list_t		 *list;
    east_list_t		 *prev;
    elabel_t		 *label;
    elabel_t		**labels;
    eint32_t		  offset;

    /* check for possible shortcuts */
    label_shortcut(function);
    for (prev = function->code, list = east_next(prev);
	 list; prev = list, list = east_next(list)) {
	node = east_node(list);
	switch (node->code) {
	    case eop_label:
		/* remove sequential labels */
		label_sequential(function, list, node->clabel.label);
		break;
	    case eop_j:				case eop_jt:
	    case eop_jf:
		/* check if target follows jump */
		list = label_redundancy(function, prev, node);
		break;
	    default:
		break;
	}
    }

    /* check if need to traverse code again */
    labels = function->labels->v.obj;
    for (offset = 1; offset < function->labels->offset; offset++) {
	label = labels[offset];
	list = elabel_list(label);
	if (east_node(list)->code == eop_label && label->jumps->offset == 0)
	    break;
    }

    if (offset < function->labels->offset) {
	/* remove labels that are not the target of any jump */
	for (prev = function->code, list = east_next(prev);
	     list; prev = list, list = east_next(list)) {
	    node = east_node(list);
	    if (node->code != eop_label)
		continue;
	    label = node->clabel.label;

	    /* if no jumps reach this label */
	    if (label->jumps->offset == 0) {
		eremove_label(function, label);

		again = true;

		east_next(prev) = east_next(list);

		/* update for next iteration */
		list = prev;
	    }
	}
    }
}

/*
 *   return start of code after label or null
 */
static east_list_t *
label_code(elabel_t *label)
{
    east_list_t		*list;

    for (list = east_next(elabel_list(label)); list; list = east_next(list)) {
	switch (east_node(list)->code) {
	    case eop_label:			case eop_block:
	    case eop_note:
		break;
	    default:
		return (list);
	}
    }

    return (null);
}

/*
 * check targets of jumps, and if the target is another jump, check if
 * can take a shortcut
 */
static void
label_shortcut(efunction_t *function)
{
    eint32_t		 i;
    ecode_t		 code;
    east_node_t		*next;
    east_node_t		*node;
    eentry_t		*iter;
    east_node_t		*jump;
    east_list_t		*link;
    east_list_t		*list;
    east_list_t		*temp;
    elabel_t		*label;
    ehash_t		*table;

    for (list = east_next(function->code); list; list = east_next(list)) {
	node = east_node(list);
    reset:
	code = node->code;
	switch (code) {
	    case eop_try:
		/* the jump after try is the exception non local jump target */
		list = east_next(list);
		break;

	    case eop_jh:
		table = els[immediate_offset(node)];
		for (i = 0; i < table->size; i++) {
		    for (iter = table->entries[i]; iter; iter = iter->next) {
			/* initialize label */
			jump = iter->value;
			label = jump->clabel.label;

			/* loop checking for possible shortcuts */
			for (;;) {
			    /* first instruction after label */
			    if ((temp = label_code(label)) == null)
				break;

			    /* check for unconditional jump after label */
			    next = east_node(temp);
			    if (next->code != eop_j ||
				next->clabel.label == label)
				break;

			    /* take shortcut */
			    if (label != next->clabel.label) {
				elabel_branch_remove(label, node);
				label = next->clabel.label;
				jump->clabel.label = label;
				elabel_branch_insert(label, node);
				again = true;
			    }
			}
		    }
		}
		break;

	    case eop_j:				case eop_jt:
	    case eop_jf:
		/* initialize */
		label = node->clabel.label;
		if ((temp = label_code(label)) == null)
		    continue;

		jump = east_node(temp);
		switch (jump->code) {
		    case eop_ret:		case eop_rett:
		    case eop_reti:		case eop_retit:
		    case eop_exit:
			/* if unconditional jump to return/exit */
			if (code == eop_j) {
			    elabel_branch_remove(node->clabel.label, node);
			    east_node(list) = jump;
			    again = true;
			}
			continue;

		    case eop_j:
		    same_jump:
			if (node->clabel.label != jump->clabel.label) {
			    elabel_branch_switch(node->clabel.label,
						 jump->clabel.label,
						 node);
			    again = true;
			    goto reset;
			}
			continue;

		    case eop_jt:
			if (code == eop_jt || code == eop_j)
			    /* same boolean test on jump to jump */
			    goto same_jump;

		    inverse_jump:
			/* jump after the always false test */
			label = ecreate_label(function);
			elabel_branch_switch(node->clabel.label,
					     label,
					     node);

			/* create new label node */
			jump = ecode_label(label);
			link = east_label_no_link(jump);

			/* insert it */
			east_next(link) = east_next(temp);
			east_next(temp) = link;

			again = true;
			goto reset;

		    case eop_jf:
			if (code == eop_jf)
			    goto same_jump;
			if (code == eop_jt)
			    goto inverse_jump;
			/* FALLTHROUGH */

		    default:
			continue;
		}
		break;

	    default:
		break;
	}
    }
}

static void
label_sequential_update(east_node_t *node, elabel_t *insert, elabel_t *remove)
{
    ehash_t		*hash;
    eentry_t		*entry;
    eint32_t		 offset;

    if (node->code == eop_jh) {
	hash = els[immediate_offset(node)];
	for (offset = 0; offset < hash->size; offset++)
	    for (entry = hash->entries[offset]; entry; entry = entry->next) {
		node = entry->value;
		if (node->clabel.label == remove)
		    node->clabel.label = insert;
	    }
    }
    else
	node->clabel.label = insert;
}

/*
 * search for sequential labels, keeping first and removing sequential ones
 */
static void
label_sequential(efunction_t *function, east_list_t *list, elabel_t *label)
{
    east_node_t		 *node;
    east_list_t		 *tail;
    east_node_t		**nodes;
    elabel_t		 *remove;
    evector_t		 *vector;
    eint32_t		  offset;

    /* keep the first label */
    tail = list;
    list = east_next(list);
    while (list) {
	/* check next opcode */
	node = east_node(list);
	if (node->code != eop_label)
	    return;

	/* sequential labels found */

	remove = node->clabel.label;

	if (remove->jumps->offset) {
	    vector = remove->jumps;
	    nodes = vector->v.obj;
	    for (offset = 0; offset < vector->offset; offset++)
		label_sequential_update(nodes[offset], label, remove);
	    /* avoid elabel_branch_insert() calls */
	    vector = label->jumps;
	    if (vector->offset + offset >= vector->length)
		erenew_vector(vector, (vector->offset + offset + 4) & ~3);
	    nodes = vector->v.obj;
	    memcpy(nodes + vector->offset,
		   remove->jumps->v.obj, offset * sizeof(eobject_t));
	    vector->offset += offset;
	}

	eremove_label(function, remove);

	/* remove label from opcode list */
	east_next(tail) = list = east_next(list);

	again = true;
    }
}

/*
 * check for redundant, zero distance jumps where the label target
 * follow the jump
 */
static east_list_t *
label_redundancy(efunction_t *function, east_list_t *tail, east_node_t *node)
{
    east_list_t		*base;
    east_node_t		*next;
    east_list_t		*list;
    east_list_t		*prev;
    east_node_t		*save;
    elabel_t		*block;
    elabel_t		*label;

    save = node;
    block = null;
    prev = east_next(tail);
    list = east_next(prev);
    label = node->clabel.label;
    for (base = null; list; prev = list, list = east_next(list)) {
	next = east_node(list);
	switch (next->code) {
	    case eop_note:
		break;

	    case eop_j:				case eop_jt:
	    case eop_jf:
		/* if intermediate jump is to same target */
		if (next->clabel.label == label) {
		    /* don't restart in case of several jumps to label */
		    base = prev;
		    node = next;
		    break;
		}

		return (prev);

	    case eop_block:
		if (block) {
		    if (base)
			return (prev);

		    again = true;

		    eremove_block(function, node->clabel.label);
		}
		block = node->clabel.label;
		break;

	    case eop_label:
		/* if label doesn't follow jump */
		if (next->clabel.label != label)
		    return (prev);

		again = true;

		/* update target list of label */
		elabel_branch_remove(label, node);

		if (base) {
		    node = save;
		    east_next(base) = list;
		    list = east_next(tail);
		    base = null;
		    /* restart loop */
		    break;
		}

		if (label->jumps->offset)
		    /* keep label */
		    east_next(tail) = list;
		else {
		    /* no jumps target label now */
		    east_next(tail) = east_next(list);
		    eremove_label(function, label);
		}

		if (block && block != label)
		    eremove_block(function, block);

		return (tail);

	    default:
		return (prev);
	}
    }

    return (prev);
}
